UVa/10154 - Weights and measures/10154.2.cpp

   1 #include <vector>
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <cassert>
   5
   6 using namespace std;
   7
   8 struct turtle{
   9   int w,s;
  10   turtle(int W, int S) : w(W), s(S) {}
  11   bool operator < (const turtle &y) const{
  12     return (s - w < y.s - y.w) ||
  13       (s - w == y.s - y.w && w < y.w) ||
  14       (s - w == y.s - y.w && w == y.w && y.s < y.w);
  15   }
  16   bool operator == (const turtle &y) const{return w == y.w && s == y.s;}
  17 };
  18 bool operator > (const turtle &x, const turtle &y){return !(x == y) && !(x < y);}
  19
  20 int main(){
  21   vector<turtle> t;
  22   int x, y;
  23   while (cin >> x >> y){
  24     assert(x <= y);
  25     t.push_back(turtle(x,y));
  26   }
  27   sort(t.begin(), t.end(), greater<turtle>() );
  28
  29   /*for (int i=0; i<t.size(); ++i){
  30     cout << "turtle[i]: " << t[i].w << " " << t[i].s;
  31     cout << endl;
  32     }*/
  33
  34   vector<int> p(t.size()), dp(t.size());
  35   for (int i=0; i<t.size(); ++i){
  36     dp[i] = 1;
  37     p[i] = t[i].s - t[i].w;
  38     for (int j=0; j<i; ++j){
  39       if (t[i].w <= p[j]){
  40         if (dp[i] < dp[j] + 1){
  41           dp[i] = dp[j] + 1;
  42           p[i] = min(p[j] - t[i].w, t[i].s - t[i].w);
  43         }
  44       }
  45     }
  46   }
  47   cout << *(max_element(dp.begin(), dp.end())) << endl;
  48   return 0;
  49 }